#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    //先对该元素进行排序
    sort(nums.begin(),nums.end());
    for(int k=0;k<nums.size();k++)
    {
        //进行剪枝操作,对于nums[k]大于target且nums[k]>0的数直接不考虑
        if(nums[k]>target&&nums[k]>=0)
            break;
        //进行去重操作
        if(k>0&&nums[k]==nums[k-1])
            continue;
        for(int i=k+1;i<nums.size();i++)
        {
            //进行剪枝操作
            if((nums[i]+nums[k])>target&&(nums[i]+nums[k])>=0)
                break;
            //进行去重操作
            if(i>k+1&&nums[i]==nums[i-1])
                continue;
            int left = i+1;
            int right = nums.size()-1;
            while(left<right)
            {
                if((long) nums[k]+nums[i]+nums[left]+nums[right] > target)
                {
                    right--;
                }
                else if((long)nums[k]+nums[i]+nums[left]+nums[right] < target)
                {
                    left++;
                } 
                else{
                    result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
                    while(right>left&&nums[right]==nums[right+1]) right--;
                    while(right>left&&nums[left]==nums[left+1]) left++;

                    //找到答案后双指针同时收缩
                    right--;
                    left++;
                }
            }
        }
    }
    return result;
}
int main()
{
    cout<<"enter a number:"<<endl;
    int target;
    cin>>target;
    cout<<"enter number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
    {
        cin>>nums[i];
    }
    vector<vector<int>> result = fourSum(nums,target);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}